{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Corporate Flight Bookings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: corpFlightBookings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #航班预订统计"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>这里有&nbsp;<code>n</code>&nbsp;个航班，它们分别从 <code>1</code> 到 <code>n</code> 进行编号。</p>\n",
    "\n",
    "<p>有一份航班预订表&nbsp;<code>bookings</code> ，表中第&nbsp;<code>i</code>&nbsp;条预订记录&nbsp;<code>bookings[i] = [first<sub>i</sub>, last<sub>i</sub>, seats<sub>i</sub>]</code>&nbsp;意味着在从 <code>first<sub>i</sub></code>&nbsp;到 <code>last<sub>i</sub></code> （<strong>包含</strong> <code>first<sub>i</sub></code> 和 <code>last<sub>i</sub></code> ）的 <strong>每个航班</strong> 上预订了 <code>seats<sub>i</sub></code>&nbsp;个座位。</p>\n",
    "\n",
    "<p>请你返回一个长度为 <code>n</code> 的数组&nbsp;<code>answer</code>，里面的元素是每个航班预定的座位总数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5\n",
    "<strong>输出：</strong>[10,55,45,25,25]\n",
    "<strong>解释：</strong>\n",
    "航班编号        1   2   3   4   5\n",
    "预订记录 1 ：   10  10\n",
    "预订记录 2 ：       20  20\n",
    "预订记录 3 ：       25  25  25  25\n",
    "总座位数：      10  55  45  25  25\n",
    "因此，answer = [10,55,45,25,25]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>bookings = [[1,2,10],[2,2,15]], n = 2\n",
    "<strong>输出：</strong>[10,25]\n",
    "<strong>解释：</strong>\n",
    "航班编号        1   2\n",
    "预订记录 1 ：   10  10\n",
    "预订记录 2 ：       15\n",
    "总座位数：      10  25\n",
    "因此，answer = [10,25]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= bookings.length &lt;= 2 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>bookings[i].length == 3</code></li>\n",
    "\t<li><code>1 &lt;= first<sub>i</sub> &lt;= last<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>1 &lt;= seats<sub>i</sub> &lt;= 10<sup>4</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [corporate-flight-bookings](https://leetcode.cn/problems/corporate-flight-bookings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [corporate-flight-bookings](https://leetcode.cn/problems/corporate-flight-bookings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,10],[2,3,20],[2,5,25]]\\n5', '[[1,2,10],[2,2,15]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        f= [0 for _ in range(n+1)] \n",
    "        for i, j, k in bookings:\n",
    "            f[i-1] += k\n",
    "            f[j] -= k\n",
    "        \n",
    "        for i in range(1,n+1):\n",
    "            f[i] += f[i-1]\n",
    "        return f[:-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        result = [0] * (n+1)\n",
    "        bookings.sort(reverse=True)\n",
    "        cur = 0\n",
    "        cur_book = bookings.pop() if bookings else None\n",
    "        stack = deque()\n",
    "        for i in range(1, n+1):\n",
    "            while stack and i == stack[0][0] + 1:\n",
    "                last_book = stack.popleft()\n",
    "                cur -= last_book[1]\n",
    "            while cur_book and i == cur_book[0]:\n",
    "                cur += cur_book[2]\n",
    "                bisect.insort(stack, cur_book[1:])\n",
    "                cur_book = bookings.pop() if bookings else None\n",
    "            result[i] = cur\n",
    "        return result[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        heapq.heapify(bookings)\n",
    "        endings = []\n",
    "        for f in range(1, n + 1):\n",
    "            while bookings and bookings[0][0] == f:\n",
    "                cur += bookings[0][2]\n",
    "                heapq.heappush(endings, bookings[0][1:])\n",
    "                heapq.heappop(bookings)\n",
    "            while endings and endings[0][0] < f:\n",
    "                cur -= endings[0][1]\n",
    "                heapq.heappop(endings)\n",
    "            ans.append(cur)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        tmp = [0]*n\n",
    "        while bookings:\n",
    "            book = bookings.pop(0)\n",
    "            tmp[book[0]-1] += book[2]\n",
    "            if book[1] <= len(tmp)-1:\n",
    "                tmp[book[1]] += -book[2]\n",
    "        new_tmp = tmp[0]\n",
    "        for i in range(1,len(tmp)):\n",
    "            new_tmp += tmp[i]\n",
    "            tmp[i] = new_tmp\n",
    "        \n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        air_seat = collections.defaultdict(int)\n",
    "        for i in range(1,n+1):\n",
    "            air_seat[i] = 0\n",
    "        tmp = [0]*n\n",
    "        while bookings:\n",
    "            book = bookings.pop(0)\n",
    "            tmp[book[0]-1] += book[2]\n",
    "            if book[1] <= len(tmp)-1:\n",
    "                tmp[book[1]] += -book[2]\n",
    "        new_tmp = tmp[0]\n",
    "        for i in range(1,len(tmp)):\n",
    "            new_tmp += tmp[i]\n",
    "            tmp[i] = new_tmp\n",
    "        \n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        ans=[0]*n\n",
    "        for i,j,k in bookings:\n",
    "            ans[i-1]+=k\n",
    "            if j<n:\n",
    "                ans[j]-=k\n",
    "        for i in range(1,n):\n",
    "            ans[i]+=ans[i-1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        a = [0] * n\n",
    "        l = len(bookings)\n",
    "        for i in range(l):\n",
    "            b = bookings[i]\n",
    "            a[b[0] - 1] += b[2]\n",
    "            if b[1] < n:\n",
    "                a[b[1]] -= b[2]\n",
    "        for i in range(1, n):\n",
    "            a[i] += a[i - 1]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        flights = [0,] * n\n",
    "        lows = bookings\n",
    "        heapq.heapify(bookings)\n",
    "        highs = [k[1:] for k in bookings]\n",
    "        heapq.heapify(highs)\n",
    "        cur = 0\n",
    "    \n",
    "        for i in range(1, n + 1):\n",
    "            #print(lows)\n",
    "            #print(highs)\n",
    "            #print(cur)\n",
    "            while len(lows) > 0 and i == lows[0][0]:\n",
    "                cur += heapq.heappop(lows)[2]\n",
    "            while len(highs) > 0 and i > highs[0][0]:\n",
    "                cur -= heapq.heappop(highs)[1]\n",
    "            flights[i-1] += cur\n",
    "        return flights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        flights = [0,] * n\n",
    "        lows = bookings\n",
    "        heapq.heapify(bookings)\n",
    "        highs = [k[1:] for k in bookings]\n",
    "        heapq.heapify(highs)\n",
    "        cur = 0\n",
    "    \n",
    "        for i in range(1, n + 1):\n",
    "            #print(lows)\n",
    "            #print(highs)\n",
    "            #print(cur)\n",
    "            while len(lows) > 0 and i == lows[0][0]:\n",
    "                cur += heapq.heappop(lows)[2]\n",
    "            while len(highs) > 0 and i > highs[0][0]:\n",
    "                cur -= heapq.heappop(highs)[1]\n",
    "            flights[i-1] += cur\n",
    "        return flights"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        segmentsArr = []\n",
    "        for i in range(len(bookings)):\n",
    "            start,end,tickets=bookings[i];\n",
    "            segmentsArr.append([start,tickets])\n",
    "            segmentsArr.append([end+1,-tickets])#防止后续需要两个while处理正负情况\n",
    "      \n",
    "        segmentsArr = sorted(segmentsArr)\n",
    "    \n",
    "        index=0;\n",
    "\n",
    "        count=0;\n",
    "        ans=[0]*n;\n",
    "        for i in range(n):\n",
    "            while index<len(segmentsArr) and segmentsArr[index][0]<=i+1:\n",
    "                count += segmentsArr[index][1]\n",
    "                index += 1\n",
    "              \n",
    "               \n",
    "            ans[i] = count\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        seats = [0] * (n+1)\n",
    "        for item in bookings:\n",
    "            seats[item[0]-1] += item[2]\n",
    "            seats[item[1]] -= item[2]\n",
    "        data = [seats[0]]\n",
    "        bookings.clear()\n",
    "        for i in range(1, n):\n",
    "            data.append(seats[i] + data[-1]) \n",
    "        return data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        answer=diff=[0]*n\n",
    "        for left,right,num in bookings:\n",
    "            diff[left-1]+=num\n",
    "            if right<n:\n",
    "                diff[right]-=num\n",
    "        for i in range(1,len(diff)):\n",
    "            answer[0]=diff[0]\n",
    "            answer[i]=diff[i]+answer[i-1]\n",
    "        return answer\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        bookings.sort()\n",
    "        pq = []\n",
    "        ans = [0] * n\n",
    "        i = 0\n",
    "        flight = 1\n",
    "        seats = 0\n",
    "        while pq or i < len(bookings):\n",
    "            if not pq:\n",
    "                flight = bookings[i][0]\n",
    "            while i < len(bookings) and bookings[i][0] == flight:\n",
    "                heapq.heappush(pq, bookings[i][1:])\n",
    "                seats += bookings[i][2]\n",
    "                i += 1\n",
    "            ans[flight - 1] = seats\n",
    "            while pq and pq[0][0] <= flight:\n",
    "                seats -= pq[0][1]\n",
    "                heapq.heappop(pq)\n",
    "            flight += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "\n",
    "        diff = [0] * n\n",
    "        for booking in bookings:\n",
    "            diff[booking[0] - 1] += booking[2]\n",
    "            if booking[1] < n:\n",
    "                diff[booking[1]] -= booking[2]\n",
    "        return list(accumulate(diff))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        arr = [0] * (n+1)\n",
    "\n",
    "        right = 0\n",
    "        for item in bookings:\n",
    "            f,l,s = item\n",
    "            l -= 1\n",
    "            f -= 1\n",
    "            arr[f] += s\n",
    "            arr[l+1] -= s\n",
    "            right = max(right, l)\n",
    "        \n",
    "        num = [0] * n\n",
    "        num[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            num[i] = num[i-1] + arr[i]\n",
    "        \n",
    "        return num\n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Difference:\n",
    "    def __init__(self, nums):\n",
    "        self.nums_length = len(nums)\n",
    "        self.diff = [0] * self.nums_length\n",
    "        self.diff[0] = nums[0]\n",
    "        for i in range(1, self.nums_length):\n",
    "            self.diff[i] = nums[i] - self.diff[i - 1]\n",
    "        self.diff_length = len(self.diff)\n",
    "\n",
    "    def increment(self, left_index, right_index, val):\n",
    "        self.diff[left_index] = self.diff[left_index] + val\n",
    "        if right_index + 1 < self.diff_length:\n",
    "            self.diff[right_index + 1] = self.diff[right_index + 1] - val\n",
    "\n",
    "    def re_struct(self):\n",
    "        res = [0] * self.diff_length\n",
    "        res[0] = self.diff[0]\n",
    "        for i in range(1, self.diff_length):\n",
    "            res[i] = res[i - 1] + self.diff[i]\n",
    "        return res\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        flight_seats = [0] * n\n",
    "        flight_diff = Difference(flight_seats)\n",
    "        for booking in bookings:\n",
    "            first = booking[0] - 1\n",
    "            last = booking[1] - 1\n",
    "            book_seats = booking[2]\n",
    "            flight_diff.increment(first, last, book_seats)\n",
    "        return flight_diff.re_struct()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        res = [0]*n\n",
    "        bookings.sort()\n",
    "        diff = defaultdict(int)\n",
    "        for f,l,s in bookings:\n",
    "            diff[f]+=s\n",
    "            diff[l+1]-=s\n",
    "        times = sorted(diff.keys())\n",
    "\n",
    "        tmp=0\n",
    "        i=0\n",
    "        for flight in range(n):\n",
    "            while i<len(times) and times[i]-1<=flight:\n",
    "                tmp+=diff[times[i]]\n",
    "                i+=1\n",
    "            res[flight]=tmp\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "\n",
    "        ret = [0] *n\n",
    "\n",
    "        for left,right,inc in bookings:\n",
    "            ret[left-1] += inc\n",
    "            if right <n:\n",
    "                ret[right] -= inc\n",
    "\n",
    "        for i in range(1,n):\n",
    "            ret[i] += ret[i-1]\n",
    "\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        res = [0] * (n + 1)\n",
    "        \"\"\"\n",
    "        for i in range(len(bookings)):\n",
    "            first = bookings[i][0]\n",
    "            end = bookings[i][1]\n",
    "            seats = bookings[i][2]\n",
    "            if seats != 0:\n",
    "                if first == end:\n",
    "                    res[first] += seats\n",
    "                else:\n",
    "                    for j in range(first, end+1):\n",
    "                        res[j] += seats\n",
    "        return res[1:]\n",
    "        \"\"\"\n",
    "        for first, end, seats in bookings:\n",
    "            res[first] += seats # 从1开始\n",
    "            if end < n: # 等于n的时候 区间已经走完了 就不需要再去减掉了\n",
    "                res[end + 1] -= seats\n",
    "        for i in range(2, n+1): # 从2开始\n",
    "            res[i] += res[i-1]\n",
    "        return res[1:]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        self.nums = [0]*n\n",
    "        self.diff = [0]*n\n",
    "        self.length = n\n",
    "        for first, last, val in bookings:\n",
    "            i = first-1\n",
    "            j = last-1\n",
    "            self.increment(i,j, val)\n",
    "        return self.result()\n",
    "\n",
    "    def increment(self, i, j, val):\n",
    "        self.diff[i]+=val\n",
    "        if j+1<self.length:\n",
    "            self.diff[j+1]-=val\n",
    "\n",
    "    def result(self):\n",
    "        res= [0]*self.length\n",
    "        res[0] = self.diff[0]\n",
    "        for i in range(1, self.length):\n",
    "            res[i] = res[i-1] + self.diff[i]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\r\n",
    "        diff = [0] * n\r\n",
    "        for i, j, k in bookings:\r\n",
    "            diff[i - 1] += k\r\n",
    "            if j < n:\r\n",
    "                diff[j] -= k\r\n",
    "        for i in range(1, n):\r\n",
    "            diff[i] += diff[i - 1]\r\n",
    "\r\n",
    "        return diff\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def corpFlightBookings(self, bookings: List[List[int]], n: int) -> List[int]:\n",
    "        diff = [0]*(n+1)\n",
    "        for i, booking in enumerate(bookings):\n",
    "            first, last, seats = booking\n",
    "            diff[first-1] += seats\n",
    "            diff[last] -= seats\n",
    "\n",
    "        res = [0]*n\n",
    "        res[0] = diff[0]\n",
    "        for i in range(1, n):\n",
    "            res[i] = res[i-1] + diff[i]\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
